//
// Created by LiuYou on 2021/12/3.
//

#include <iostream>
#include <vector>
#include <random>
#include <iterator>


static int randomNumberFromTheRange(int left, int right) {
    std::random_device randomDevice;
    std::default_random_engine randomEngine( randomDevice());
    std::uniform_int_distribution<> uniformIntDistribution( left, right );
    return uniformIntDistribution( randomEngine );
}


static void shellSort(std::vector<int>& arr) {
    for (int gap = arr.size() / 2; gap > 0; gap /= 2) {

        for (int i = gap; i < arr.size(); ++i) {
            // todo 笔记: 这里的循环条件一定是 j >= gap, 而不是 j > gap。
            //  而且注意: 这里 int j = i; 而不是 int j = i - 1; 注意和插入排序这个相同的位置的代码的不同！
            for (int j = i; j >= gap; j -= gap) {
                if (arr[j] < arr[j - gap]) {
                    std::swap( arr[j], arr[j - gap] );
                }
            }
        }

    }
}


int main(int argc, char** argv) {
    std::vector<int> arr( 10 );
    for (auto& item: arr) {
        item = randomNumberFromTheRange( 0, 100 );
    }

    std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
    std::cout << std::endl;

    shellSort( arr );

    std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
    std::cout << std::endl;


    return 0;
}
